package history.study.dynamic_programming;

// 746. 使用最小花费爬楼梯

/**
 *  1. dp[i] 爬上第i个台阶最小花费
 *  2. 递推公式：dp[i] = math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
 *  3. dp[1] = 0, dp[2] = 0;
 *  4. 从前往后进行遍历
 *  5. dp[3] = dp[1]+dp[0] = 1
 *     dp[3] = dp[1]+dp[2] = 2
 */
public class LeetCode_746 {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        if (length <=1) return 0;
        int []state = new int[length+1];
        state[1] = 0;
        state[2] = 0;
        for (int i = 2; i <= length; i++) {
            state[i] = Math.min(state[i-1]+cost[i-1], state[i-2]+cost[i-2]);
        }
        return state[length];
    }
}
